All Questions
5 questions
23votes
1answer
1kviews
Is the 2016 implementation of Shor's algorithm really scalable?
In the 2016 Science paper "Realization of a scalable Shor algorithm" [1], the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of [2] and Table 5 ...
- 541
12votes
4answers
4kviews
Factoring as a decision problem
I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision ...
- 495
4votes
2answers
431views
Impacts of quantum computing on Theoretical Computer Science [closed]
Using quantum computers we can do calculations very fast. However from a layman's view, I want to know the impact of quantum computers have on Theoretical computer science.
- 149
9votes
1answer
706views
On optimality of Grover algorithm with high success probability
It is well-known that bounded error quantum query complexity of the function $OR(x_1,x_2,\ldots, x_n)$ is $\Theta(\sqrt{n})$. Now the question is what if we want our quantum algorithm to succeed for ...
4votes
2answers
511views
Major advance for measurement based quantum computing?
http://arxiv.org/abs/1211.3405 The Measurement Based Quantum Computing Search Algorithm is Faster than Grover's Algorithm If this recent paper is true, it seems like a major advance for ...
- 357
